#
# @lc app=leetcode.cn id=15 lang=python3
#
# [15] 三数之和
#

# @lc code=start
from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        if not nums or nums[len(nums) - 1] < 0:
            return []
        for i in range(0, len(nums) - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, len(nums) - 1
            while j < k and nums[k] >= 0:
                result = nums[i] + nums[j] + nums[k]
                if result == 0 and [nums[i], nums[j], nums[k]] not in ans:
                    ans.append([nums[i], nums[j], nums[k]])
                    k -= 1
                    while j < k - 1 and nums[k] == nums[k + 1]:
                        k -= 1
                    j += 1
                    while j + 1 < k and nums[j - 1] == nums[j]:
                        j += 1
                elif result > 0:
                    k -= 1
                    while j < k - 1 and nums[k] == nums[k + 1]:
                        k -= 1
                else:
                    j += 1
                    while j + 1 < k and nums[j - 1] == nums[j]:
                        j += 1
        return ans

    def threeSum2(self, nums: List[int]) -> List[List[int]]:
        positive = [i for i in set(nums) if i > 0]
        negative = [i for i in set(nums) if i < 0]
        hash = {}
        for i in nums:
            if i in hash:
                hash[i] += 1
            else:
                hash[i] = 1
        if 0 in hash and hash[0] > 2:
            ans = [[0, 0, 0]]
        else:
            ans = []
        if not (positive and negative) or len(nums) < 3:
            return ans
        for j in negative:
            for i in positive:
                result = -(i + j)
                if result == i and hash[i] > 1:
                    ans.append([j, i, i])
                elif result == j and hash[j] > 1:
                    ans.append([j, j, i])
                elif result in hash and j < result < i:
                    ans.append([j, result, i])
        return ans


if __name__ == "__main__":
    s = Solution()
    threeSum = s.threeSum

    print(threeSum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]])
    print(threeSum([0, 0, 0, 0]) == [[0, 0, 0]])
    print(threeSum([]) == [])
# @lc code=end
